/**
 * 【最大价值】
 * 选/不选 每个物品只能选一个
 * 数据结构：二维数组
 * 
 * ======定义======
 * dp[i][j] 1～i个物品经过选择,放入后背包容量为j 的最大价值
 * 公式 01放或者不放
 * dp[i][j] = max(dp[i-1][j]---没有放, dp[i-1][j-weights[i]]+values[i]---放了)
 * 
 * ======初始化======
 * 1-全部为0
 * 2-只放物品0，容量weight[0]~w, 价值是value[0] dp[0][j]=values[0]
 * 
 * ======遍历======
 * i=0-->i
 * j=0-->w
 * 
 */
/**
 * 相关题目：
 * 不同路径v1 v2
 * 不同搜索二叉树
 * 整数拆分
 * 分割等和子集
 * 一和零
 * 目标和
 * 最后一块石头的重量
 */
/**
 * 
 * @param {*} values  物品i价值
 * @param {*} weights 物品i重量
 * @param {*} w 背包容量
 * @returns 
 */
const backage=(values, weights, w) => {
  const m = values.length;
  //选择一维数组还是二维数组
  const dp = Array(m+1).fill().map(i=> Array(w+1).fill(0)); //dp(m,w)
  //遍历， 把dp连续填满
  for(let i=1;i<=m;i++){
    for(let j=1;j<=w;j++){
      if(j<weights[i-1]){
         //放不下当前物品i
        dp[i][j] = dp[i-1][j]
      }else {
        //放的下物品i，选择放/不放价值最大的一个, 
        //为什么i-1? 因为i从1开始， 所以对于weights、values i-1是当前物品
        dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1]);
      }
    }
  }
  return dp[m][w];
}
/**
 * 优化为一维数组
 * j背包容量倒序遍历
 * dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
 * 遍历i起点可以为0
 * 
 * 外层物品，内层容量，不能改变，保证容量是倒顺
 */
const backage1=(values, weights, w) => {
  const m = values.length;
  const dp = Array(w+1).fill(0);
  //对i~m个物品进行依次选择
  for(let i=0;i<m;i++) {
      //! 容量倒叙保证物品只放入一次 j从0～w被确定， 随着i的循环不断更新
    for(let j=w;j>=weights[i];j--) {
      // max(不放的价值， 放的价值=不放的价值+当前物品价值)
      dp[j] = Math.max(dp[j], dp[j-weights[i]]+values[i])
    }
  }
  return dp[w];
}
let values = [15, 20, 30];
let weights = [1, 3, 4];
let w = 4;
console.log('01背包', backage(values, weights, w)); //35


/**
 * ✅review12.09
 */
